package src.leetcode.backtrack.medium_0077;

import java.util.ArrayList;
import java.util.List;

public class combine {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.combine(4, 2));
    }
}


class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> ans = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            List<Integer> list = new ArrayList<>();
            list.add(i + 1);
            combineHelper(i + 1, k - 1, n, list, ans);
        }

        return ans;
    }

    private void combineHelper(int i, int k, int n, List<Integer> list, List<List<Integer>> ans) {
        if(k == 0) {
            ans.add(list);
        }else{
            for (int j = i + 1; j <= n; j++) {
                List<Integer> newList = new ArrayList<>(list);
                newList.add(j);
                combineHelper(j, k - 1, n, newList, ans);
            }
        }
    }
}